import random as R
import math

LEVEL_SIZES = [(5,5), (6,5), (7,6), (8,6), (9,7), (10,7), (11,7)]
LEVEL_GEMS = [
    [(1,2), (2,1), (1,3), (3,1), (2,2)],
    [(1,2), (2,1), (1,3), (3,1), (2,2)],
    [(1,2), (2,1), (1,3), (3,1), (2,2)],
    [(1,2), (2,1), (1,3), (3,1), (2,2)],
    [(1,2), (2,1), (1,3), (3,1), (2,2)],
    [(1,2), (2,1), (1,3), (3,1), (2,2)],
    [(1,2), (2,1), (1,3), (3,1), (1,3), (3,1), (2,2), (2,2), (3,3)],
]
TRIED = -1
UNUSED = -2

def placegem(LV, sim_times=1000)->float:
    """LEVEL_SIZES里面是每个关卡的大小（宽，高），LEVEL_GEMS里面的每个array是对应关卡中的每个宝石的大小（宽，高），
    这段代码需要对每个关卡进行sim_times次模拟，
    每次模拟的过程是：
    0. 针对每个关卡，模拟sim_times次;
    1. 按照LEVEL_SIZES里面的宽高，生成一个空的二维数组;
    2. 将LEVEL_GEMS里面的每个宝石放入这个二维数组中，放置的方式是随机的，但是不能重叠;
    3. 接下来模拟玩家在关卡中，寻找宝石的过程，统计需要多少次才能找到所有的宝石（必须把宝石占据的所有格子都找到）;
       3.1 玩家看不到宝石，只能看到空格和已经找到的宝石;
    4. 统计所有的模拟中，找到所有宝石的平均次数，返回这个值;
    """
    def can_place(grid, x, y, gem_width, gem_height):
        """Check if a gem can be placed at position (x, y) without overlapping."""
        for i in range(gem_height):
            for j in range(gem_width):
                if grid[y + i][x + j] >= 0:
                    return False
        return True
    
    def do_place_gem(grid, x, y, gem_width, gem_height, gi):
        """Place a gem on the grid."""
        for i in range(y, y+gem_height):
            for j in range(x, x+gem_width):
                grid[i][j] = gi

    def is_valid(x, y, width, height, found):
        """Check if the position (x, y) is valid for any non-found gem placement. """
        for i, (gem_width, gem_height) in enumerate(gems):
            if i in found: continue
            for yoff in range(gem_height):
                ny = y - yoff
                for xoff in range(gem_width):
                    nx = x - xoff
                    if nx<0 or nx+gem_width>width or ny<0 or ny+gem_height>height: continue

                    ok = True
                    for h in range(gem_height):
                        if not ok: break
                        for w in range(gem_width):
                            if grid[ny + h][nx + w] == TRIED: 
                                ok = False
                                break;
                    if ok: return True                    
        return False        

    def simulate_player(grid):
        """Simulate the player finding gems."""
        found = set()
        attempts = 0
        width, height = len(grid[0]), len(grid)
        while len(found) < len(LEVEL_GEMS[LV]):
            x = R.randint(0, width - 1)
            y = R.randint(0, height - 1)
            # Ensure the player doesn't pick the same cell twice
            if grid[y][x] == TRIED: continue
            if not is_valid(x, y, width, height, found): continue
            cellv = grid[y][x]
            if cellv >= 0:
                found.add(grid[y][x])
                attempts += gems[cellv][0] * gems[cellv][1]  # Add the size of the gem to attempts
                # Mark the gem as found by setting its cells to TRIED
                for i in range(height):
                    for j in range(width):
                        if grid[i][j] == cellv:
                            grid[i][j] = TRIED
            else:
                attempts+=1
                grid[y][x] = TRIED  # Mark the cell as tried

        return attempts
    
    def _recur_place(ix, gems, grid, width, height):
        """Recursively place gems on the grid."""
        if ix >= len(gems):
            return True
        gem_width, gem_height = gems[ix]
        try_times = 0
        while try_times < 10:
            x = R.randint(0, width - gem_width)
            y = R.randint(0, height - gem_height)
            if can_place(grid, x, y, gem_width, gem_height):
                do_place_gem(grid, x, y, gem_width, gem_height, ix)
                if _recur_place(ix + 1, gems, grid, width, height):
                    return True
                # Backtrack
                for i in range(y, y + gem_height):
                    for j in range(x, x + gem_width):
                        grid[i][j] = UNUSED
            else:
                try_times += 1
        return False
    
    # 3. 接下来模拟玩家在关卡中，寻找宝石的过程，统计需要多少次才能找到所有的宝石（必须把宝石占据的所有格子都找到）;
    total_attempts = 0
    for t in range(sim_times):
        # 1. 按照LEVEL_SIZES里面的宽高，生成一个空的二维数组;
        level = LEVEL_SIZES[LV]
        width, height = level
        grid = [[UNUSED for _ in range(width)] for _ in range(height)]

        # 2. 将LEVEL_GEMS里面的每个宝石放入这个二维数组中，放置的方式是随机的，但是不能重叠;
        gems = LEVEL_GEMS[LV]
        if not _recur_place(0, gems, grid, width, height):
            raise Exception(f"Gem placement failed: times: {t}")
        attempts = simulate_player(grid)
        total_attempts += attempts

    # 4. 统计所有的模拟中，找到所有宝石的平均次数，返回这个值;
    return total_attempts / sim_times

def sim_levels():
    """对所有的关卡进行模拟，返回每个关卡的平均次数"""
    results = []
    for i in range(len(LEVEL_SIZES)):
        avg_attempts = placegem(i, 1000)
        results.append(avg_attempts)
    return results

if __name__=='__main__':
    # 运行模拟
    results = sim_levels()
    for i, result in enumerate(results):
        print(f"Level {i + 1}: Average attempts to find all gems: {result:.2f}")
